Crypto CTF 2022: keydream (crypto)

問題概要

素数$ p,qの上位ビットと下位ビット、および$ n=pqがわかっているときに$ p,qを求めて、RSA暗号で復号する。

問題スクリプト

code:py

from Crypto.Util.number import *

import string

from flag import flag

def randstr(l):

rstr = [(string.printable:62 + '_')getRandomRange(0, 62) for _ in range(l)]

return ''.join(rstr)

def encrypt(msg, l):

while True:

rstr = 'CCTF{it_is_fake_flag_' + randstr(l) + '_90OD_luCk___!!}'

p = bytes_to_long(rstr.encode('utf-8'))

q = bytes_to_long(rstr::-1.encode('utf-8'))

if isPrime(p) and isPrime(q):

n = p * q

e, m = 65537, bytes_to_long(msg.encode('utf-8'))

c = pow(m, e, n)

return n, c

n, c = encrypt(flag, 27)

print(f'n = {n}')

print(f'c = {c}')

解法

Coppersmith's Attackが可能。Coppersmith's Methodを使えば法$ nの約数に対してもsmall rootsが求められる。

今回の問題だと、'CCTF{it_is_fake_flag_' + randstr(l) + '_90OD_luCk___!!}'のrandstr(l)部分を変数にして法が素数$ pのときのsmall rootsを求める。

defund/coppersmithを用いて、

code:py

from Crypto.Util.number import *

load("coppersmith.sage")

R = Integers(n)

P.<x> = PolynomialRing(R, 1)

L = 27

H = b"CCTF{it_is_fake_flag_"

T = b'_90OD_luCk___!!}'

p = bytes_to_long(H) * 2 ** ((L+ len(T))*8) + x * 2 ** (len(T)*8) + bytes_to_long(T)

bounds = ((2**(27*8)),)

small_roots(p, bounds, m=15, d=15)

[(35946296645795027706081981764759243051730930874638102982427961697,)]が得られる。

long_to_bytes(35946296645795027706081981764759243051730930874638102982427961697)を出力すると、b'Waoq1JixM5ACgjynbkNj9Ctldiaが得られ、ダミーフラグはCCTF{it_is_fake_flag_Waoq1JixM5ACgjynbkNj9Ctldia_90OD_luCk___!!}だとわかる。

あとは復号するだけ。

code:sage

p = bytes_to_long(b"CCTF{it_is_fake_flag_Waoq1JixM5ACgjynbkNj9Ctldia_90OD_luCk___!!}")

q = n // p

e = 65537

d = pow(e, -1, (p-1)*(q-1))

long_to_bytes(int(pow(c, d, n)))

Flag: CCTF{h0M3_m4dE_k3Y_Dr1vEn_CrYp7O_5ySTeM!}

余談

small_roots()の実行時間を早くしたい場合は、$ n/qの末尾ビットが$ pの末尾ビットになることを利用すると良い。

上のスクリプトの変数Tがdia_90OD_luCk___!!}になり未知部分が3文字減って高速化できる。

CCTF{it_is_fake_flag_の文字数が$ 21だから法を$ 2^{21\cdot 8}のもとで考える。

$ pの末尾21文字（一部未知）の値と$ qの末尾21文字（既知）の値を掛けた値が$ nになる。

code:sage

m = 2 ** (len(H)*8)

q_tail = bytes_to_long(H::-1)

p_tail = ((n % m) * (inverse_mod(q, m) % m)) % m

long_to_bytes(p_tail)